package 代码随想录.数组.二分查找;

import java.lang.annotation.ElementType;
import java.util.logging.XMLFormatter;

/**lc69：Sqrt(x)
 * link：https://leetcode-cn.com/problems/sqrtx/
 * @author ChenweiLin
 * @create 2021-11-29 14:27
 */
public class sqrtX {
    public static void main(String[] args) {
        System.out.println(mySqrt(5));
    }

    public static int mySqrt(int x) {
        //特殊情况
        if (x == 0 || x == 1)
            return x;
        //二分查找
        int left = 1;
        int right = x/2;
        while (left < right){
            int mid = left+((right - left + 1)/2);
            if(x/mid >= mid){//(mid*mid) < x 可能会使(mid*mid)溢出 因此使用除法
                left = mid;
            }else{
                right = mid - 1;
            }
        }

        return left;

    }
}
